class Solution {
public:
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
    int cutOffTree(vector<vector<int>>& forest)
    {
        int m = forest.size();
        int n = forest[0].size();
        set<int> order;
        for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (forest[i][j] != 0 && forest[i][j] != 1) order.insert(forest[i][j]);
        int ans = 0;
        pair<int, int> beg = make_pair(0, 0);

        function<int(pair<int, int>&, int)> minpath = [&](pair<int, int>& start, int end)->int {
            if (forest[start.first][start.second] == end) return 0;
            queue<pair<int, int>> q;
            q.push(start);
            int ret = 0;
            vector<vector<bool>> vis(m, vector<bool>(n, false));
            vis[start.first][start.second] = true;
            while (q.size())
            {
                int count = q.size();
                ret++;
                for (int i = 0; i < count; i++)
                {
                    pair<int, int> f = q.front();
                    for (int a = 0; a < 4; a++)
                    {
                        int x = dx[a] + f.first, y = dy[a] + f.second;
                        if (x >= 0 && x < m && y >= 0 && y < n && forest[x][y] != 0 && !vis[x][y])
                        {
                            if (forest[x][y] == end)
                            {
                                start = make_pair(x, y);
                                return ret;
                            }
                            q.push(make_pair(x, y));
                            vis[x][y] = true;
                        }
                    }
                    q.pop();
                }
            }
            return -1;
            };

        for (auto e : order)
        {
            int x = minpath(beg, e);
            if (x == -1)
                return -1;
            ans += x;
        }
        return ans;
    }
};